The present invention relates generally to methods of data encoding and decoding for error correction, and more particularly to interleaving for turbo-codes.
With the advent of modern information theory and the definition of Shannon""s Limit it was determined that any given noisy communications channel has a finite, non-zero threshold above which a message cannot be transmitted with a guarantee of error free transmission. The establishment of Shannon""s Limit was what is considered an existence proof, that is, it establishes that a coding method can be derived that reaches the defined limits for communicating over a noisy channel, but does not show how such a code may be derived.
In 1993, in a paper by C. Berrou, A. Glavieux, and P. Thitimajshima entitled xe2x80x9cNear Shannon Limit Error Correcting Coding ad Decoding: Turbo Codesxe2x80x9d, Proceedings of ICC""93, Geneva, Switzerland, pp. 1064-1070, May 1993, a new communications scheme referred to as turbo coding was disclosed. This communications code offered transmissions near Shannon""s Limit, as has in the ensuing years been modified numerous times to eke out any last performance advantage. Turbo codes (TC), like many other codes, used controlled redundant information, and interleaving to allow a decoder to correct for noise induced errors. The attention paid to turbo codes since 1993 is related to their powerful error correcting capability, reasonable complexity, and flexibility in terms of providing different block sizes and code rates.
One common turbo-code encoder consists of two 16-state, rate xc2xd recursive systematic convolutional (RSC) encoders operating in parallel with be data bits interleaved between the two encoders, as shown in FIG. 1. FIG. 1 illustrates a standard turbo code encoder 100, with a data stream di, which is provided to the modulator (not shown), RSC1102, and the interleaver 104. The interleaver reorders the bits of data stream di according to a predetermined set of indices, and provides its output to RSC2106. The outputs of RSC1102 and RSC2106 ci1 and ci2 respectively are sets of parity bits that are provided to a standard puncturing unit 108, whose output is provided to a modulator (not shown). The feedback and feedforward polynomials used herein are (23, 35) octal, respectively. Other polynomials and number of states could also be used. Without puncturing, the overall code rate is ⅓. This is because the systematic data bits, di, are only included once. Higher code rates can be achieved by puncturing the code parity bits ci1 and ci2. (In some cases it can be beneficial to puncture a small number of systematic data bits, di, to improve flare performance, as will be shown.) Good interleaver spreading properties are desirable for both fast convergence and good distance properties. High (Hamming) distance is desirable for both lowering the so-called xe2x80x9cerror floorxe2x80x9d or are and for making the flare as steep as possible. Hamming distance is the minimum number of symbols in a block that must be changed for a first codeword to become a second codeword. The further apart two blocks are, the more a block can be corrupted while retaining the ability for the decoder to properly decode the message. It is also important to reduce the number of codewords at or near the minimum distance.
RSC codes are often terminated with flush bits. Flush bits are employed because they increase the Hamming distance between codewords. The cost of the introduction of flush bits is a penalty in the code rate. A method of obtaining the benefits of the increased distances found in terminated RSC codes without the code rate penalty is to encode the RSC code in a circle. This technique is referred to as tail-biting. Tail-biting increases the distances of an RSC code without employing flush bits. If both RSC codes in a turbo encoder are either terminated or tail-biting the encoder is described as either dual terminating or dual tail-biting as the case may be. Though the design of dual terminating or dual tail-biting encoders must account for the presence of an interleaver, the design of the interleaves need not be varied.
Interleaving is a practice well known in the art. It is a method of arranging or permuting the elements within a block. In a turbo-code encoder the elements are typically data bits or data symbols. In a turbo-code decoder the data elements are typically soft data samples from the receiver.
Interleaving is a key component of turbo-codes, as shown in FIG. 1. Two interleavers that have been commonly investigated are the xe2x80x9crandomxe2x80x9d interleaver and the so-called xe2x80x9cS-randomxe2x80x9d or xe2x80x9cspreadxe2x80x9d interleaver. The random interleaver simply performs a random or pseudo-random permutation of the elements without any restrictions.
Golden relative prime, golden, and dithered golden interleavers have previously been applied to the design of turbo-codes. Good error rate performance has been reported for small to medium sized blocks (on the order of 1000 data bits). These interleavers can be generated quickly and have excellent spreading properties. Even though the worst-case low-distance codewords are usually eliminated golden interleavers can still produce a large number of low-distance codewords, related to the regular structure of the interleaver.
Another recent interleaver design method tries to select the interleaver indexes by minimizing the correlation between the extrinsic inputs. Not surprisingly, the designed interleavers tend to have high-spread characteristics. It is also true in general that interleaves with high-spread characteristics tend to produce extrinsic values with low correlation. This is because the new definition of spread is inherently well matched to providing low extrinsic correlation.
FIG. 2 illustrates the components of a conventional interleaver 104 in the context of the encoder 100. The input of the interleaver is stored in a memory 110, which is at least as large as the interleaver block size (K symbols). An indexing engine 112, re-orders the symbols stored in the memory 110 according to the order provided by the indices 114. The re-ordered symbols are stored in memory 116 and provided as output. In some cases the interleaver can provide the re-ordered symbols directly without the need for memory 116.
The following is a general review of S-random interleavers. Interleavers can be defined and implemented in a number of different ways. FIG. 3 shows the definition used herein. The interleaver reads from a vector of input symbols or samples, vin, and writes to a vector of interleaved or permuted output samples, vout. The output samples are written sequentially using the time index i, i=0 . . . Kxe2x88x921, where K is the size of the interleaver. Vector I defines the order that the samples in the input vector are read. That is, the i-th output, written to location i in the output vector, is read from location I(i) in the input vector. With this model, the interleaved is completely defined by the integer read vector I. This illustration is used for definition purposes only, and does not necessarily represent a preferred method of implementation. As another example, vector I could define the write order.
The xe2x80x9cS-randomxe2x80x9d interleaver is a semi-random interleaver. It is based on the random selection, without replacement, of K integers from 0 to Kxe2x88x921, but with the following constraint: each randomly selected integer is compared to the Jxe2x88x921 most recently selected integers. If the current selection is within Jxe2x88x921 of at least one of the previous Jxe2x88x921 integers, then it is rejected and a new integer is selected until the condition is satisfied.
This process is repeated until all K integers are extracted. The search time increases with J, and there is no guarantee that the process will finish successfully.
Note that J denotes the one-sided span of write indexes considered at each step, including the current index and ignoring edge effect. An appropriate (old) definition of spread, based on the S-random algorithm, for span J, and write indexes i and j, is as follows:
Sxe2x80x3old(J,i,j)=|I(i)xe2x88x92I(j)|,for|ixe2x88x92j| less than jxe2x80x83xe2x80x83(1) 
The (minimum) spread associated with index i, for a given span J, is then defined as                                           S            old            xe2x80x2                    ⁡                      (                          J              ,              i                        )                          =                              min                          lJ              =              1                                ⁢                      ⌊                                          S                old                xe2x80x3                            ⁡                              (                                  J                  ,                  i                  ,                  j                                )                                      ⌋                                              (        2        )            
The (minimum) spread associated with the entire interleaver, for a given span J, is then defined as                                           S            old                    ⁡                      (            J            )                          =                              min            l                    ⁢                      [                                          S                old                xe2x80x2                            ⁡                              (                                  J                  ,                  i                                )                                      ]                                              (        3        )            
For tail-biting turbo-codes all relevant operations should be performed modulo-K. With the above definitions, it is obvious, to one of skill in the art, that the spread of an interleaver designed using the S-random algorithm is at least the span J. That is, if the algorithm finishes successfully, then Sold(J)xe2x89xa7J. In practice, one finds that the spread achieved is almost always equal to J for large values of J. The theoretical maximum spread for an S-random interleaver is (typically) floor ({square root over (K)}), for a span of the same. (There are exceptions depending on the specific values of K and J, and the boundary conditions, but this is a good general approximation, especially for large values of K.) As a rule of thumb, however, the choice J less than {square root over (K/2)} produces a solution in a reasonable amount of time. As an example, with a block size of K=512 data bits, the maximum theoretical spread is 22, but it is difficult to obtain a spread higher than 16, using the S-random algorithm.
It would be disingenuous to claim that the performance of conventional interleavers is poor. Although performance of conventional interleavers is good, improvements to interleavers can be easily applied to many existing communication systems to yield added performance.
It is therefore desirable to provide a practical interleaving system and method with relatively lower packet error rate (PER) and bit error rate (BER). It is further desirable to provide a method for modifying any interleaver to improve the distance spectrum for a specific turbo-code.
It is an object of the present invention to obviate or mitigate at least one disadvantage of prior art, specifically it is an object of the present invention to provide a method and system for interleaving elements to obtain a high spread.
In a first aspect, the present invention provides a method of determining interleaving indices for an interleaver, acting elements, comprising determining a minimum acceptable spread, spread being measured as the minimum of the sum of the distance between two elements prior to being interleaved, and the distance between the same two elements after being interleaved, over all pairs of elements, for each element, selecting an index from a predefined set of indices, the selected index maintaining the minimum acceptable spread and sorting the selected index elements to provide a quantized integer index vector. In an embodiment of the present invention the predetermined set of indices is a subset of the set of real numbers, such as (0,K), and the step of selecting an index includes randomly selecting an index from the predetermined set, and discarding any index if the minimum acceptable spreading goal is not maintained.
According to a further aspect of the present invention, there is provided a a method of determining interleaving indices for interleaving K elements comprising the step of defining a set of at least K points, which are optionally arranged as rows and columns that are separated from each other by {square root over (K)} units, offsetting the points by varying the location of each point, defining the predefines set of indices as a subset of K point from the set of at least K points and determining a set of interleaving indices from the subset of K points. In a further embodiment, the rows and columns are parallel to the x and y axes, and the set of points is rotated, optionally by 45xc2x0 prior to defining the predefined set. In other embodiments of the present invention the distances that the points are offset is taken from a randomly distributed set of distances, the points are offset in a direction parallel to one of the rows or columns of the set, all the points in a row or column are offset by a same amount independent of other rows or columns. In yet a further embodiment, K is twice the value of a perfect square, and an equal offsetting distance is applied to all points in a given rows       K    2  
away from the given row, and       K    2  
is relatively prime to the repetition period of a feedback polynomial associated with the interleaving process. In another embodiment the set of determining includes sorting the selected index element to provide a quantized integer index vector.
According to yet a another aspect of the present invention, there is provided an interleaver for a communications system comprising an input memory for receiving K elements from an input, an output memory for providing K elements to an output and an indexing engine for interleaving the K elements received from the input memory, in accordance with a quantized integer index vector, and providing the interleaved elements to the output memory, the interleaving indices being determined by determining a minimum acceptable spread, spread being measured as the minimum of the sum of the distance between two elements prior to being interleaved, and the distance between the same two elements after being interleaved, over all pairs of elements, for each element, selecting an index from a predefined set of indices, the selected index maintain the minimum acceptable spread and sorting the selected index elements to provide the quantized integer index vector. In an embodiment of the present aspect of the invention the indices are determined by randomly selecting an index from a set of possible indices, the selected index maintaining the minimum acceptable spreading goal in combination with the previously selected indices.
In a further aspect, there is provided an interleaver for a communications system comprising an input memory for receiving K elements from an input, an output memory for providing K elements to an output, an indexing engine for interleaving the K elements received from the input memory, in accordance with a quantized integer index vector, and providing the interleaved elements to the output memory, the interleaving indices being determined by defining a set of at least K points offsetting the points by varying the location of each point by a distance, defining a set of possible indices as a subset of points in the set of at least K offset points and determining the quantized integer index vector from K selected points from the set of possible indices.
In yet a further aspect of the present invention, there is provided a method of encoding a set of elements in a communication system comprising receiving a set of elements, encoding a first copy of the received set with a recursive systematic convolutional code, interleaving a second copy of the received set according to a set of interleaving indices providing a minimum spread, spread being measured as the minimum of the sum of be distance between two elements prior to being interleaved, and the distance between the same two elements after being interleaved, over all pairs of elements, encoding the interleaved copy with a recursive systematic convolutional code, puncturing the received set, the encoded first copy and the encoded interleaved copy, and transmitting the punctured set, the punctured encoded copy and the punctured encoded interleaved copy to a modulator.
Other aspects and features of the present invention will become apparent to those ordinarily skilled in the art upon review of the following description of specific embodiments of the invention in conjunction with the accompanying figures.